#include <iostream>
#include <vector>
using namespace std;




/*
背包问题的变形
就是把问题变成了把石头分两堆，两堆的重量最接近
a b c d 是四块石头

a - c -> e
d - e -> f
b - f 最小

b - (d - (a - c)) -> 最小
b - d + a - c = (a + b) - (c + d) 最小
意思就是分两堆，差最小
*/ 
int lastStoneWeightII(vector<int>& stones) {
    int sum = 0;
	vector<int> dp(1600, 0);
    dp[0]=1;
	for (auto stone : stones)
	{
		sum += stone;
		for (int i = 1500; i - stone >= 0; i--)
		if (dp[i - stone])
			dp[i] = 1;
	}
	for (int i = sum/2 ; i >= 0; i--)
		if (dp[i])
            return (sum - i) - i;
	return 0;
}

int main()
{

}
